package pers.vic.basics.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Vic.xu
 * @description: 39. 组合总和  回溯  {@literal https://leetcode-cn.com/problems/combination-sum/}
 * @date: 2020/12/3 0003 8:47
 */
public class J0039_M_CombinationSum {
    /*
    给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的数字可以无限制重复被选取。
    说明：
    所有数字（包括 target）都是正整数。
    解集不能包含重复的组合。 
     */

    /**
     * 这又是一道典型的回溯，我来试试看
     * 1. 每个元素可重复使用
     * 2. 先把数组排序， 这样只要探测到当前元素比target小，就可以直接终止往下搜索
     * 3. 为了防止重复结果集，在某个元素的全部组合探测完毕后，下一次探测就不再使用它
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> combination = new ArrayDeque<Integer>();
        Arrays.sort(candidates);
        dfs(candidates, result, combination, target, 0);
        return result;
    }

    /**
     * 我也知dfs是  Depth-First-Search  但是回溯怎么说的？ backtracking algorithm
     */
    public static void dfs(int[] candidates, List<List<Integer>> result, Deque<Integer> combination, int target, int begin) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = begin; i < candidates.length; i++) {
            int cur = candidates[i];
            if (target < cur) {
                return;
            }
            combination.add(cur);
            dfs(candidates, result, combination, target-cur, i);
            combination.removeLast();
        }

    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        // [7],[2,2,3]
        for (List<Integer> integers : combinationSum(candidates, target)) {
            String collect = integers.stream().map(String::valueOf).collect(Collectors.joining("-", "", ""));
            System.out.println(collect);
        }

    }

}
